<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<title>CS45: Lab 3</title>

<style type="text/css">
@import url("style/stylesheet_hw.css");
</style>
</head>

<body> 
<div id="Wrapper"> 
  <div id="HeadImgMed"> 
    <div id="HeaderSmall">
	    <h1>CS45 Lab 3: Implementing a Synchronization Primative</h1>
	  </div>
	  <div class="TagLine">
           <b>Due Thursday March 6 before 11:59pm</b>
           <br>Checkpoint due Monday Feb. 24 at the begining of Lab
	  </div>
  </div> <!--Header image box-->


  <div id="Content">
<h4>For the Checkpoint Implement:</h4> 
<ol><li>  Two of the required system calls,
<tt>event_open</tt> and <tt>event_print</tt>.  For the checkpoint version 
of event_print, print out Event table information about opens 
(you can add printing out information about waiters later, after the checkpoint).
<li> and the <tt>event_init</tt> function.  
</ol>
You will demo your checkpoint
to me during your Monday lab session.  You cannot use late days on the 
checkpoint.

<hr>
<h4>Content:</h4>
<ul>
<li><A HREF="#intro">Problem Introduction</A>  
<li><A HREF="#startpt">Starting point code and new VirtualBox image</A>  
<li><A HREF="#details">Implementation Details</A>  
<li><A HREF="#started">Tips for Getting Started</A>  
<li><A HREF="#testing">Testing your Code</A>  
<li><A HREF="#handin">What to Hand in and Demo</A>
<li><A HREF="#demo">Lab Demo and Preparing for your Demo</A>
<li><A HREF="#refs">Links to Resources</a>
</ul>
<p> This lab will be done with your forever CS45 lab partner: 
<a href="machinespartners.php">Lab partners and machine assignments</a>

<br>
<div class="TagLine" id="intro">Introduction</div>

For this project you will implement and test a new synchronization primitive
called an <i>Event</i>.   User-level processes will use Events in 
the following way:
<ol>
<li> open an Event
<li> wait and signal on Events they have opened
<li> close an Event
</ol>
Multiple processes can use Events to synchronize their actions by each opening
the same Event and then calling event_wait and event_signal on it.  Your 
solution must ensure that only processes that open an Event can call
<tt>event_wait</tt>, <tt>event_signal</tt> or <tt>event_close</tt> 
on the Event.  
The lifetime of an Event is the period of time from its first open 
(when it is created) to the time of its last close (when it is destroyed).  
Only the last close of an Event destroys it. 
<p>
The semantics of <tt>event_wait</tt> are that is always blocks the 
calling process.  The semantics of <tt>event_signal</tt> are that it 
unblocks <b>all</b> processes waiting on the Event.
<p>
You will implement the data structure(s) for representing Events at the 
kernel-level, and you will add system calls for user-level processes to 
<tt>event_open</tt>, <tt>event_close</tt>, <tt>event_wait</tt>, 
and <tt>event_signal</tt> on Events.  In addition, you will need to write 
user-level programs to test your Event primitives.
<p>
An individual process can have multiple Events open at a time (and can 
wait and signal on any of its open Events).  Your Event implementation,
however, must make sure that only processes that open an Event can wait, 
signal, or close the Event.
<p>
<font color="red">I strongly encourage you to get an early start on 
this project;</font> your solution will require a fair amount of thinking 
time, linux code reading time, and code design and debugging 
time.

<br>
<br>
<div class="TagLine" id="startpt">Starting point code and Virtualbox image</div>

In this week's lab you will grab a new virtualbox image to use for lab3
and start with a new copy of the Linux source with a new config file 
to build the kernel in a different way.
<p>
Start by setting up a git repo for your lab3 work.  Make sure
to add three users to your git repo: you, your partner, and your
shared CS45 account.
<p>
Both you and your partner should then clone a copy into your
private <tt>cs45/labs</tt> subdirectory.
<a href="http://www.cs.swarthmore.edu/~newhall/cs45/s14/Labs/git_setup.html">here</a> are the instructions for setting up a git repo from lab1.
<p>
Then one of you or your partner can copy over some starting point
code into your repo, add and push it.  I included an example gitignore
file with the starting point code.  First move it to .gitignore before
adding and pushing it (and add in any names of executable files or other
files you do not want git to add to your repo).
<pre>
$ cp ~newhall/public/cs45/lab03/* .
$ ls
  Makefile README event.c gitignore tester.c
$ mv gitignore .gitignore
$ git add .gitignore
$ git add *
$ git commit
$ git push origin master
</pre>
The starting point code contains files with most of the #includes that 
you will need, and includes them in the correct order (there are some
dependencies on include order of some some kernel header files, so be careful
if you add more #includes ).  It also includes a Makefile and starting point
for a user-level test program (mostly some guesses at #includes are given
to you).


<br>
<br>
<div class="TagLine" id="details">Implementation Details</div>

<h4>Creating an Event Table</h4>

To implement support for Event primitives, you need to create 
kernel data structure(s) to keep track of Events that have been 
created (i.e. an Event table), to keep track of which 
processes currently have the Event open, to keep track of which processes 
are currently blocked on an Event, etc.  Typically, the 
kernel uses fixed-sized data structures to keep track of instances of
abstractions that it implements.  For example, there is an open file table
to keep track of all currently open files in the system.  Because these
data structures are fixed-sized, there is an upper bound on the number of
instances that can currently exist in the system (e.g. there is a maximum
number of open files, number of processes and threads, ...).
<p>
Implement your Event Table data structure
as a <tt>static</tt> global variable of a 
fixed-sized, and make its size small (~5) so that you 
can test that you are handling the case when a process requests to open
a new Event, but there are already 5 active Events (each has at least
one open). Calls to event_open in this case should return an error indicating
that no more Events can be created.   When an Event is closed for the last 
time, it is no longer an active Event, and space for it in the Event 
Table can be used by a subsequent newly created Event.

<h4>Initializing the Event Table</h4>

When the kernel boots it initialize all of its 
data structures.  If you add a data structure to the kernel to keep track
of Events, you need to have the kernel initialize it on start-up.  To do
this implement an <tt>event_init</tt> function and then
register it as an init function to be invoked on start-up, using
the <tt>pure_initcall</tt> macro:
<pre>
// NOTE: this is NOT a system call it is a function called by 
//       the kernel during its boot sequence to initialize state
//       you need for your event implementation  
static int  __init event_init() {
  // code to initialize Event data structures and other state
}

// to register the event_init function to be called during boot sequence:
pure_initcall(event_init);
</pre>


<h4>Dynamic Memory Allocation in the Kernel</h4>

Although the Event Table itself should be statically allocated, there
may be some Event state that needs to be dynamically allocated due
to it depending on the set of processes currently using an Event.
<p>
<tt>kmalloc</tt> and <tt>kfree</tt> are kernel-level routines for dynamic
allocation of kernel memory.  Use <code>GFP_KERNEL</code> as the priority value 
passed to <code>kmalloc</code>.
<p>
Memory leaks in the kernel are very, very
bad; make sure that if you add a call kmalloc you add a corresponding call
to kfree somewhere.  Also, it is
good programming practice to set a variable's value to NULL after freeing
the space to which it points: <code> free(ptr); ptr = 0; </code>.
<p>

<h4>Event System call</h4>

You will implement the following system calls for performing operations
on Events (use the SYSCALL_DEVINEX macros to generate the function definitions
though):
<ol>
<li><b>
<tt> long event_open(int *id)</tt></b>: if *id==0, then create a 
new Event, and set the id to the new Event's ID.  If *id is positive, 
open an existing Event with a matching id value.  The function returns 0 
on success, or an error value on failure.  Return different error values
to indicate different types of failure (you may use error values 
already defined in <tt>error.h</tt>, for example: <code>return -ESRCH;</code>).
Remember, that you need to verify that values passed by reference to
your system calls refer to readable/writable memory before you  
read/write to it (see project 2 if you forgot how to do this).  
A process can only open the same event 1 time.
<p>
<li><b>
<tt> long event_close(int id)</tt></b>: closes the corresponding Event.
The last close to an Event, destroys the Event (you could re-use its id
for a subsequent event_open call that is passed a value of 0).
Only processes that have the Event open can close the Event.  Also, 
the last close should fail if there are waiters on the Event.
The function returns 0 on success, or an error value on error.
<p>
<li><b>
<tt> long event_wait(int id)</tt></b>: blocks the calling process on
the Event with a matching id (again the caller must have opened the Event
before it can wait or signal or close it).  The function returns 0 on
success, or an error value on error.
<p>
<li><b>
<tt> long event_signal(int id)</tt></b>: wakes up <b>all</b> processes
blocked on the event with the matching id.  The function returns 0 on
success, or an error value on error.  Again, only processes that have
opened the Event can signal on it.
<p>
<li><b>
<tt> long print_event_table()</tt></b>: a debugging routine to 
print out the contents of the event table (printk).  For open events, 
include the process ids of every process that has the event open, 
and print out the pid of all processes waiting on each event.
returns 0 on success. 
</ol>
<p>

<h4>Blocking and Unblocking a Process (task)</h4>

You are <font color="red">required </font>  to implement 
blocking processes on Events and waking-up process waiting on Events 
in the following way (don't use other higher-level kernel 
functions that you may find):
<p>
You will use wait_queue_head_t data structure(s) to block processes that
call event_wait on an Event.
<p>
To <b>block</b> a process on an Event, you need to:
<ol>
<li> set the process' state (in its task_struct) to 
TASK_INTERRUPTIBLE or TASK_UNINTERRUPTIBLE
(you should use TASK_INTERRUPTIBLE for this assignment, which means that
if the process receives a signal (like SIGKILL), it will wake up before 
event_signal is called on the Event on which it is blocked.
<li> add the process to a wait queue associated with the Event
<li> call the kernel routine <tt>schedule()</tt> to de-schedule the 
process and schedule another process from the READY Q to run.
</ol>
<p>
To <b>wake-up</b> a process on an Event, you need to:
<ol>
<li> remove the process from its waitQ
<li> set its state so that it will get put back on the readyQ
(see code in wait.h that does this)
<li> do a bunch of other stuff
<li> call <tt>schedule()</tt> to add it to the readyQ
</ol>
<b>OR</b> you may use the kernel's <tt>wake_up</tt> functions
(in <code>wait.h</code> that calls function in <code>sched.c</code>)
to do much of this for you, but make sure you understand what this 
function is doing...<b>just use the wake_up functions</b> don't try to write your own.
<p>
<h4>Wait Queues</h4>
You should use the linux kernel wait queue data structures for
keeping track of all processes waiting on an Event.  Your code will need to
include linux/wait.h and linux/sched.h.  The wait queue data structure uses 
Linux's doubly linked list implementation (in linux/list.h), and consists
of a wait_queue_head struct that contains a list of wait_queue_t structs (one
for each task waiting on the wait queue).  
<p>
Your solution should <b>NOT</b> make calls to the higher level functions
<code>interruptible_sleep_on,  or sleep_on</code>.  Instead, you will 
implement a solution that explicitly adds a process to a waitqueue
and blocks it using the 3 steps listed above.  
You may, however, use <code>wake_up</code> to 
wake up all waiters on a wait queue.
<p> 
The wait queue data structure is a bit tricky to 
figure out.  I suggest looking at existing code the initializes, adds 
and removes items from a wait queue, and draw some pictures and step 
through the code for init_waitqueue_head, init_waitqueue_item, 
add_wait_queue, and remove_wait_queue on your picture.
<p>
To iterate through the elements on a wait queue, you can use the
list_for_each_safe macros, and the list_entry macro to 
get a pointer to the next wait_queue_t element in the list.
Here are some example code fragments using wait_queues 
(<font color="red">note:</font> there
are other ways to declare and initialize wait queues, and how you
do so depends on the context in which you are using them, this is 
just one example):
<pre>
  // declare and init a wait Q
  static DECLARE_WAIT_QUEUE_HEAD(my_wait_Q);  

  // declare and initialize a wait_queue_t element named "wait_entry"
  struct task_struct *curtask = get_current();
  DECLARE_WAITQUEUE(wait_entry, curtask);   

  // there are functions to add and remove elements from a wait Q:
  add_wait_queue(&amp;my_wait_Q, &amp;wait_entry);
  remove_wait_queue(&amp;my_wait_Q, &amp;wait_entry);

  // you can traverse the elements of a wait queue using the underlying
  // list implementation used by the wait queue (see wait.h and list.h )
  struct list_head *tmp, *next;	
  list_for_each_safe(tmp, next, &amp;(my_wait_Q.task_list)) {
      wait_queue_t *curr = list_entry(tmp, wait_queue_t, task_list);
      ...
  }
</pre>
The best way to figure out how to use wait queues is to look at kernel
code that uses them (and look for different types of uses), and look
through the wait.h file for macros, type defs, and functions you can use.
As a rule of thumb, avoid using anything starting with an underscore.
<p>
<h4>Synchronization Primitives in the kernel</h4>
You will likely need to add synchronization code to some or all of your
system call implementations.  Think about the fact that multiple processes
can be simultaneously running in kernel mode in any of your system call
functions.  Are there Event data structures or state to which you need
to ensure atomic access?
If so, then those parts should be in a critical section.
Look in linux/semaphore.h for the semaphore implementation.  Here is some
example code using semaphores:
<pre> 
    static DECLARE_MUTEX(event_mutex); // declare a MUTEX semaphore initialized to 1
    static DECLARE_MUTEX_LOCKED(event_mutex); // declare a MUTEX semaphore initialized to 0 

    if(down_interruptible(&amp;event_mutex)) {
          // process woke up due to signal...semaphore was NOT acquired	
    }  
    // Critical Section Code (i.e. access shared data structures)
	  // make sure this process doesn't block while it holds the semaphore
    up(&amp;event_mutex)) {
</pre>

You may not, however, use semaphores as the blocking and unblocking machanism
for blocking and ublocking processes that call event_wait and event_signal.
<p>
<h4>Other requirements</h4>
Your Event implementation should be in a new source file that you add 
to the kernel. 
<p>
Your system calls should return error values as they did in the previous
assignment (for example, <code>return -ESRCH</code>).  It is fine to use
existing error values defined in <code>error.h</code> that are close to but 
perhaps not exactly what you want for your errors.  You may add new error 
codes if you'd like, but it is not required.  User level
programs should call <code>perror</code> to print out an error message
whenever a call to one of your system calls returns an error.
</ol>

<br>
<br>
<div class="TagLine" id="started">Tips for Getting Started</div>

This project will require a lot of reading of Linux source code to get an
idea of what you need to do and how to do it.  Your solution will likely
be about 300-500 lines of code (including your well written comments).  
Start by examining Linux source code that
does something similar to what you need to do (block a process on an Event
and wake up all processes waiting on the Event when an signal on an Event 
occurs) I'd suggest looking at some of the source files code in 
ipc/ and in sched.c.  In addition, you will want to look at implementations 
of some of the functions you will use in your solution such as the 
functions that add to, remove from, and init a wait_queue.
<p>
As you design your solution, think about what a process is (or can be) doing
while another process is modifying shared state associated with an Event.
For example: is it possible for process i to do a wait on Event j,  process k
to do a signal on Event j, and process i to do another wait on Event j before
it has been removed from Event j's wait queue (add itself to the wait Q more
than one time)?  can a process exit while it is on an Event wait queue?
when does a process' call to <code>schedule()</code> return (what is true
about the process at this point)?  
<p>
I suggest incrementally implementing and testing functionality.  Start with
event_init, then event_open and test that a process can successfully open 
several Events, and that you are correctly detecting error conditions.  
As you go, implement partally functionality of event_print to print out 
information about the Event functionality you have implemented.
<p>
You will likely want to add a fair amount of debugging code as you 
implement and test.  The output from <code>printk</code> statements 
is written to files: <code>/var/log/messages and /var/log/kern.log</code>.
It can also be echoed to the console by <code>sudo dmesg -n 7</code>
<p>
Use good modular design...remember you can have regular kernel-level 
functions that your system calls call.

<br>
<br>
<div class="TagLine" id="testing">Testing</div>
Implement a test application(s) that you can use to test all your system
calls.  Make sure to test all the different conditions  
of multiple and single processes synchronizing on Events (including 
handling of error conditions).  Here are some cases to consider (this
is not an exhaustive list):
<ul>
<li> Multiple processes open an event 
<li> One process waiting when event_signal is called 
<li> No processes waiting when event_signal is called 
<li> Multiple processes waiting when event_signal is called 
<li> More than max number of new Event opens are attempted 
<li> One process closes an Event which has multiple opens
<li> The last process closes an Event
<li> Trying to open/close/signal/wait on an invalid Event number
<li> Trying to close/signal/wait on an Event that the process has not opened.
</ul>
Keep in mind that your implementation of Event does not have to prevent
user-level programs from using Events in a bad way.  For example, if two
processes open the same Event to synchronize their actions, and they both 
do an event_wait on the Event, they will both block indefinitely (deadlock).
This is not a problem with your implementation, but a problem with the
user-level program's use of Events.  There may, of course, be hanging
behavior that is caused by bugs in your implementation, and these you 
must fix.  As you debug, it is important to be careful about what you are 
testing, so that if your program hangs you know whether it is due to a 
bug in your Event implementation or a bug in your test program.
<p>
When you call system calls from your test program, get and check the
return value.  If the return value is -1, you should call <tt>perror</tt> 
to print out an error specific message.
<p>
Again, use information in <tt>/proc</tt> to help you debug your 
program's correctness.

<br>
<br>
<div class="TagLine" id="handin">What to Handin</div>

Submit the following using 
<a href="../../howto_runninghandin.html">cs45handin</a>
<b>Only one of you or your partner should submit your tar file 
via cs45handin</b>. If you accidentally both submit it, send me email 
right away letting me know which of the two solutions I should keep and 
which I should discard.
<p>
Create a single 
<a href="http://www.cs.swarthmore.edu/~newhall/unixhelp/howto_tar.html">tar</a> file with the following and submit it using cs45handin:
<ol>
<li> README file containing the following information:
  <ol>
  <li> Your name and your partner's name
  <li> The number of late days you used on this assignment
  <li> The number of late days you have used so far
  <li> A brief (1 paragraph) description of how you implemented the Event 
       synchronization primitive.  Include
       information about any design choices you made and why you made them.
  <li> A list of the source file that you modified or added (and are submitting)
       please list these as full path names.  For example:
<pre> 
 Files we added
 -------------- 
 # implementation of my new sys calls
 /usr/src/linux/kernel/mynewfile.c  
 ...	
 Files we modified
 ----------------- 
 # added a call to my function foo in function blah:
 /usr/src/linux/kernel/existinfile.c 
 ...
</pre>
  <li> The full path, and machine name, to the .deb packages with your
       lab3 kernel image and headers files.  For example:
<pre>
 @garlic:/local/me_and_pal/linux-headers-2.6.32.44-lab3_1.0_amd64.deb  
 @garlic:/local/me_and_pal/linux-image-2.6.32.44-lab3_1.0_amd64.deb  
</pre>
  Immediately before, or after, running cs45handin, rebuild the kernel_image 
and kernel_header packages (the Option 1 build) so that they contain your 
latest lab3 updates (in case you have been doing a bzImage build).  
Then DO NOT MODIFY AFTER THE DUE DATE.  
  </ol>
<p>
<li> Copies of the test program(s) you wrote including Makefile(s).  These 
     should be well commented including descriptions the functionality that 
     you are testing at different points in your program, and including a
     description of how to run your test program.  You may additionally
     submit an output script of your test program annotated with comments 
     describing what you are testing at each part (it is not necessary
     that you submit this, and only do so if you think that it helps to 
     explain how your test program works).  
<p>
<li> Copies of every kernel source and header files that you 
modified or added for this lab. <b>I only want the files you modified 
or added</b>, do not submit a tar file containing the entire kernel source
tree.
</ol>



<br>
<br>
<div class="TagLine" id="demo">Demo and Preparing for Demo</div>

After submitting your project, you and your partner will sign-up for a 
20 minute demo slot.  You should demonstrate all completely working 
functionality of your system calls as well as your handling of error 
conditions.  I will definitely want to see cases where both single and
multiple processes are waiting on an Event.  
<p>
I recommend writing a <b>simple</b>, generic, interactive test program 
for your demo.  It would provide a 
menu of system call options, read in the user's next option (and any
additional input needed for that option), and 
then makes a call the user's selected system call. After each such selection,
you can then show me the results of that particular system call by using 
information from /proc, ps, top, etc. or by calling print_event_table.  
This is as opposed to writing a test program that contains all the calls 
you want to demo and just streams through them.  The idea is to be able 
to stop after each system call and show me what happened as a result 
of that call, demonstrating that the call did what it is supposed to do.
And, then show me the results of another system call, and so on.  
<p>
A simple test program with a menu of system call options that a user can
select any one after another, can be used to show
any sequence of system calls: it should be easy to write and
extremely flexible for showing all kinds of different scenerios.
<p>
The print_event_table system call will be useful for showing the
effects of the other system calls.  However, you may also want to run 
a version of your kernel with some additional debugging printks if it 
helps you to demonstrate that your solution is really blocking processes 
when it should be and really waking them up when it should be or any other
effects of operations on Events.  


<br>
<br>
<div class="TagLine" id="refs">Links to Useful Resources</div>
<ul>
<li> <a href="http://www.cs.swarthmore.edu/~newhall/unixhelp/virtualbox.php">
Virtual Box Guide for CS45 Labs</a>  
<p>
<li> <a href="../../howto_runninghandin.html">cs45handin</a>
<li> <a href="http://www.cs.swarthmore.edu/~newhall/unixlinks.html#linux">
links to Linux programming resources</a>
<li> <a href="http://www.cs.swarthmore.edu/~newhall/unixlinks.html#Clang">
C programming resources</a>
</ul>



</div> <!--content--> 
<div id="Footer">
<p>
<!--Common footer text/images-->
<br>
<small>
<!--File/php last-edited time stamping-->
Last updated: Tuesday, March 04, 2014 at 11:46:57 AM</small>
</div>
</div> <!--wrapper-->
</body>
</html>
